/*
题目描述：连续数组的最大和
方法：
动态规划
 */
public class E42 {
    public static void main(String[] args) {
        int[] array = {6,-3,-2,7,-15,1,2,2};
        int res = FindGreatestSumOfSubArray(array);
        System.out.println(res);
    }

    public static int FindGreatestSumOfSubArray(int[] array) {
        int max = 0;
        int sum = 0;
        for(int i = 0; i < array.length; i++){
            if(sum < 0){
                sum = array[i];
            }
            else{
                sum += array[i];
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}
